from collections import defaultdict
from typing import List


class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides_dict = defaultdict(list)
        for start, end, tip in rides:
            rides_dict[start].append([end, tip])

        dp = [0] * (n + 1)
        for start in range(1, n + 1):
            dp[start] = max(dp[start], dp[start - 1])  # 从上个位置空载过来
            for end, tip in rides_dict[start]:
                dp[end] = max(dp[end], dp[start] + (end - start) + tip)

        return dp[-1]


if __name__ == "__main__":
    print(Solution().maxTaxiEarnings(n=5, rides=[[2, 5, 4], [1, 5, 1]]))  # 7
    print(Solution().maxTaxiEarnings(n=20, rides=[[1, 6, 1], [3, 10, 2], [10, 12, 3], [11, 12, 2], [12, 15, 2],
                                                  [13, 18, 1]]))  # 20
